#ifndef _QUAD_TREE_H_
#define _QUAD_TREE_H_

#include <vector>
#include <list>
#include "contest_interface.h"

class QNode;
class QLeafNode;
class QInternalNode;

class QuadTree {
public:
    uint8_t dimension;
    QNode* root;
    AttributeType* keyType;

public:
    QuadTree(void);
    QuadTree(uint8_t dim, KeyType type);
    ~QuadTree(void);

    QLeafNode * searchBucket_InsertRecord(Record * record);
    QLeafNode * searchBucket_ModifyRecord(Record * record);
    //First sort the bucket before splitting to find median and then split on the basis of that median
    QInternalNode* splitOptimal(QLeafNode* currentL);

    ErrorCode insert(Record * _record);
    ErrorCode delete_Record(Record *r, uint8_t duplicateFlag);
    ErrorCode update_Record(Record *record, Block *new_payload, uint8_t flags);
    void setSplitter(Key key, QInternalNode* newInternalNode);
    void sortBucketList(QLeafNode* currentL, std::list< Record*>* sortedListRecord);

    /*Fake functions to be called by Transaction before commit*/
    ErrorCode can_InsertRecord(Record * record, Transaction * tx);
    ErrorCode can_ModifyRecord(Record * record, Transaction * tx, uint8_t duplicateFlag,
            Iterator** itRecords);

    ErrorCode PartialSearch(Key key, Iterator ** it, std::vector< int> *ls, int s);
    ErrorCode PointSearch(Key key, Iterator ** it);
    ErrorCode RangeSearch(Key min, Key max, Iterator ** it);

    ErrorCode PartialSearchHelper(Key key, QInternalNode *q, Iterator **records,
            std::vector< int> *ls, int s);
};

#endif /*_QUAD_TREE_H_*/

